/**********************************************************************************************/
/* FBL_ArraySet.cpp																			  */
/*                                                                       					  */
/* Copyright Paradigma, 1993-2006                                       					  */
/* All Rights Reserved.                                                 					  */
/**********************************************************************************************/

#include <VShared/FBL/publ/Headers/StdAfx.h>

#include <VShared/FBL/publ/Sets/FBL_ArraySet.h>
#include <VShared/FBL/publ/Sets/FBL_BitSet.h>

#include <VShared/FBL/publ/Sets/FBL_BitSetIterator.h>
#include <VShared/FBL/publ/Sets/FBL_ArraySetIterator.h>

#include <VShared/FBL/publ/Errors/FBL_Exceptions.h>

#include <algorithm>


/**********************************************************************************************/
FBL_Begin_Namespace


/**********************************************************************************************/
void qsort_long( ulong* first, ulong* last );


/**********************************************************************************************/
ArraySet::ArraySet( ulong ioLimitCount ) 
{ 
	InitSelf( ioLimitCount ); 
}


/**********************************************************************************************/
// Class of list of records IDs. 
//
ArraySet::ArraySet( const ArraySet& inSet )
{	
	// new array will get size EXACTLY as number of items in the inSet.
	// i.e. we do not copy empty space. 
	ulong inItems = inSet.get_Count();
	
	InitSelf( inItems );
	
	memcpy( pStart, inSet.begin(), inItems * sizeof(ulong) );
	pFinish = pStart + inItems;
	
	isSorted = inSet.isSorted;
}


/**********************************************************************************************/
// Convert bit vector to the ArraySet.
// Note, Array is sorted automatically !!!
//
ArraySet::ArraySet( const BitSet& inSet, ulong ioLimitCount )
{
	InitSelf( inSet.get_Bits_1_Count() ); 
	
	SetIterator_Ptr iter = inSet.get_Iterator();
	SetIterator& refIter = *iter;

	ID_TYPE id;
	if( (id = refIter.FirstItem()) != 0 )
	{			
		do
		{
			Append( id );
		}
		while( (id = refIter.NextItem()) && ioLimitCount-- ); 
	
		put_IsSorted( true );
	}		
}


/**********************************************************************************************/
ArraySet::~ArraySet( void )
{
	if( pStart )
		delete [] pStart;
		
	pStart 		= NULL;
	pFinish 	= NULL;
	pStorageEnd = NULL;			
}


/**********************************************************************************************/
void ArraySet::InitSelf( ulong inMaxCount )
{	
	if( inMaxCount )
	{
		pStart 		= new ID_TYPE[inMaxCount];	
		pFinish 	= pStart;
		pStorageEnd = pStart + inMaxCount;
	}
	else
	{
		pStart 		= NULL;	
		pFinish 	= NULL;
		pStorageEnd = NULL;	
	}
	
	isSorted = false;
}


#pragma mark -
#pragma mark ====== Set API ======= 


/**********************************************************************************************/
SetIterator_Ptr ArraySet::get_Iterator( void ) const
{
	return new ArraySetIterator( *this );
	
}


/**********************************************************************************************/
// Remove inItem from the array.
//
void ArraySet::Remove( ID_TYPE inItem )
{
	ID_TYPE* p;

	/* At first try to find inItem */
	if( isSorted )
		p = STD::lower_bound( pStart, pFinish, inItem );	
	else 
	{
		p = pStart;
		while( p < pFinish && *p != inItem )
			p++;
	}	

	/* If found remove it */
	if( p < pFinish )
		 RemoveAt( (ulong)(p - pStart + 1 ) );

}


/**********************************************************************************************/
// Can as grow, so and reduse size of set. Can truncate exisitng data.
// If NewItemsCount is 0 then free memory.
// Note, require additional memory.
//
void ArraySet::Resize( ulong NewItemsCount )
{
	if(NewItemsCount == 0 && pStart )	// we want free memory
	{
		delete [] pStart;

		pStart 		= NULL;
		pFinish		= NULL;
		pStorageEnd = NULL;
	
	}else	
	{
		ID_TYPE* pTmp = new ID_TYPE[NewItemsCount];
		ID_TYPE	Count = get_Count();
			
		// Chose min value:
		// If NewItemsCount is less we trucate existing data.
		Count = Count < NewItemsCount ? Count : NewItemsCount;
		
		if( pStart )
		{
			memcpy( (char*)pTmp, (char*)pStart, Count * sizeof(ID_TYPE) ); 
			delete [] pStart;
		}


		// fill by zero rest items if any.
		memset( pTmp + Count, 0, NewItemsCount - Count ); 

		pStart 		= pTmp;
		pFinish		= pStart + Count;
		pStorageEnd = pStart + NewItemsCount;
	}
}


/**********************************************************************************************/
// If array was changed directly throw pointers (for speed) then you must set right 
// position of pFinish marker. 
//
void ArraySet::SetItemsCount( ID_TYPE inNewCount )
{
	ID_TYPE theCount = get_MaxCount();

	if( inNewCount < theCount )	// min().
		theCount = inNewCount;

	pFinish = pStart + theCount;	
}


/**********************************************************************************************/
// Sorts items in array in ascending order by values.
//
void ArraySet::Sort( void ) throw()
{
	if( !isSorted )
	{
		ID_TYPE Count = get_Count();
		if( Count )
		{
			qsort_long( pStart, pStart + Count - 1 );
			isSorted = true;
		}
	}
}


/**********************************************************************************************/
// Check space before adding new data.
// If there is no more space, resize array, but not more than inMaxPossible.
//
void ArraySet::Tune( ulong inMaxPossible )
{
	if( get_Count() == get_MaxCount() )
	{
		ID_TYPE NewCount = 2 * get_MaxCount();
		
		if( NewCount == 0 )
			NewCount = 10;
		
		Resize( NewCount < inMaxPossible ? NewCount : inMaxPossible );
	}		
}


/**********************************************************************************************/
// Returns true if given Number is in list. The top bound of list is limited by Count.
//
bool ArraySet::Include( ID_TYPE inItem ) const
{
	if( pStart == pFinish )
		return false;
	
	if( isSorted )
		return STD::binary_search( pStart, pFinish, inItem );
	else
	{
		// perform linear search:
		ID_TYPE* p = pStart;
		while( (p < pFinish) && (*p != inItem) )
			p++;
			
		return bool( p < pFinish );	
	}	
}


/**********************************************************************************************/
Set* ArraySet::Clone( bool inCopy ) const throw()
{ 
	return inCopy ? new ArraySet(*this) : new ArraySet(get_MaxCount());  
}


#pragma mark -
#pragma mark ====== Set Operations with other Set ======= 


/**********************************************************************************************/
Set_Ptr ArraySet::Union( const Set_Ptr inSet )
{
	if( inSet == NULL )
		return Clone();
		
	ArraySet_Ptr pArraySet = fbl_dynamic_cast<ArraySet>( inSet.get() ); 

	if( pArraySet )
	{
		return this->Union( pArraySet );
	}
	else
	{
		FBL_CHECK( false ); // FIXME.
		return NULL;
	}
}


/**********************************************************************************************/
Set_Ptr ArraySet::Intersection( const Set_Ptr inSet )
{
	if( inSet == NULL )
		return NULL;
		
	if( ArraySet_Ptr pArraySet = fbl_dynamic_cast<ArraySet>(inSet.get()) )
	{
		return Intersection( pArraySet );
	}
	else if( BitSet_Ptr pBitSet = fbl_dynamic_cast<BitSet>(inSet.get()) )
	{
		ArraySet_Ptr arraySet = new ArraySet(*pBitSet.get());
		return Intersection( arraySet );
	}

	return NULL;
}


/**********************************************************************************************/
Set_Ptr ArraySet::Difference( const Set_Ptr inSet )
{
	if( inSet == NULL )
		return Clone();

	ArraySet_Ptr pArraySet = fbl_dynamic_cast<ArraySet>( inSet.get() ); 

	if( pArraySet )
	{
		return this->Difference( pArraySet );
	}
	else
	{
		FBL_CHECK( false ); // FIXME.
		return NULL;
	}
}


/**********************************************************************************************/
Set_Ptr ArraySet::SymmetricDifference	( const Set_Ptr inSet )
{
	if( inSet == NULL )
		return Clone();

	ArraySet_Ptr pArraySet = fbl_dynamic_cast<ArraySet>( inSet.get() ); 

	if( pArraySet )
	{
		return this->SymmetricDifference( pArraySet );
	}
	else
	{
		FBL_CHECK( false ); // FIXME.
		return NULL;
	}
}
 

#pragma mark -
#pragma mark ====== I_Serializable API ======= 


/**********************************************************************************************/
void ArraySet::From( 
	I_IStream_Ptr inStream,
	bool		  inBlock )
{
	argused1(inBlock);

	// Destroy existing content first.
	InitSelf(0);

	// 1) Allocated len.
	ulong allocLen;
	inStream->get(allocLen);

	if( allocLen > 0 )
	{
		InitSelf(allocLen / sizeof(REC_ID));

		// 2) Actual len.
		ulong actualLen;
		inStream->get(actualLen);
		if( actualLen > 0)
		{
			// 3) BitSet's data.
			inStream->get((uchar*)pStart, actualLen);
			pFinish = pStart + (actualLen / sizeof(REC_ID));

			// 4) 'Sorted' flag.
			inStream->get(isSorted);
		}
	}
}


/**********************************************************************************************/
void ArraySet::From( 
	I_PacketRcv* 	inPacket,
	bool		  		inBlock )
{
	argused1(inBlock);

	// Destroy existing content first.
	InitSelf(0);

	// 1) Allocated len.
	ulong allocLen = inPacket->get_ULongParam();

	if( allocLen > 0 )
	{
		InitSelf(allocLen / sizeof(REC_ID));

		// 2) Actual len.
		ulong actualLen = inPacket->get_ULongParam();
		if( actualLen > 0)
		{
			// 3) BitSet's data.
			inPacket->get_BinaryParam( pStart, actualLen );
			
			pFinish = pStart + (actualLen / sizeof(REC_ID));

			// 4) 'Sorted' flag.
			isSorted = inPacket->get_BoolParam();
		}
	}
}


/**********************************************************************************************/
void ArraySet::To( 
	I_OStream_Ptr inStream,
	bool		  inBlock ) const
{
	argused1(inBlock);
	
	// Type of set.
	inStream->put(uchar(1));

	if( pStart )
	{
		ulong allocLen = static_cast<ulong>((pStorageEnd - pStart) * sizeof(ulong));
		ulong actualLen = static_cast<ulong>((pFinish - pStart) * sizeof(ulong));

		// 1) Allocated len (in bytes).
		inStream->put(allocLen);

		if( actualLen > 0 )
		{
			// 2) Actual len (in bytes).
			inStream->put(actualLen);
			
			// 3) Data of actual len.
			inStream->put((uchar*)pStart, actualLen);

			// 4) 'Sorted' flag.
			inStream->put(isSorted);
		}
		else
		{
			inStream->put(0UL);
		}
	}
	else
	{
		inStream->put(0UL);
	}
}


/**********************************************************************************************/
void ArraySet::To( 
	I_PacketSnd*	inPacket,
	bool		  	inBlock ) const
{
	argused1(inBlock);
	
	FixParamCount fixParamCount( inPacket );
	
	// Type of set.
	inPacket->put_UCharParam(uchar(1));

	if( pStart )
	{
		ulong allocLen = static_cast<ulong>((pStorageEnd - pStart) * sizeof(ulong));
		ulong actualLen = static_cast<ulong>((pFinish - pStart) * sizeof(ulong));

		// 1) Allocated len (in bytes).
		inPacket->put_ULongParam(allocLen);

		if( actualLen > 0 )
		{
			// 2) Actual len (in bytes).
			inPacket->put_ULongParam(actualLen);
			
			// 3) Data of actual len.
			inPacket->put_BinaryParam( pStart, actualLen );

			// 4) 'Sorted' flag.
			inPacket->put_BoolParam(isSorted);
		}
		else
		{
			inPacket->put_ULongParam(0UL);
		}
	}
	else
	{
		inPacket->put_ULongParam(0UL);
	}
}


#pragma mark -
#pragma mark ====== ArraySet Methods: ======= 


/**********************************************************************************************/
// Make new list of adresses - intersection of pA and pB.
//
ArraySet_Ptr ArraySet::Intersection( ArraySet_Ptr pList ) throw()
{
	if( pList == NULL )
		return NULL;

	ArraySet_Ptr pA = this;
	ArraySet_Ptr pB = pList;
		
	ID_TYPE CountC = pA->get_Count();

	if( pB->get_Count() < CountC )
		CountC = pB->get_Count();

	ArraySet_Ptr pC = new ArraySet( CountC );	
	
	if( CountC )
	{
		pA->Sort();
		pB->Sort();
		
		pC->pFinish = STD::set_intersection( 
								pA->pStart, pA->pFinish, 
						  		pB->pStart, pB->pFinish, 
						  		pC->pStart );
	
	}
	
	pC->isSorted = true;
		
	if( pC->get_IsEmpty() )
	{
		return NULL; 
	}
	else
	{
		return pC;
	}
}


/**********************************************************************************************/
// Make new list of adresses - union of pA and pB.
//
ArraySet_Ptr ArraySet::Union( ArraySet_Ptr pList ) throw()
{
	if( pList == NULL )
		return (ArraySet*) Clone();

	ArraySet_Ptr pA = this;
	ArraySet_Ptr pB = pList;
		
	pA->Sort();
	pB->Sort();
	
	ID_TYPE CountC = pA->get_Count() + pB->get_Count();
	ArraySet_Ptr pC = new ArraySet( CountC );	
	
	if( CountC )
	{
		pC->pFinish = STD::set_union( 
								pA->pStart, pA->pFinish, 
								pB->pStart, pB->pFinish, 
								pC->pStart );	
	}
	
	pC->isSorted = true;

	if( pC->get_IsEmpty() )
		return NULL; 
	else
		return pC;
}


/**********************************************************************************************/
// Make new list of adresses - difference of pA and pB.
//
ArraySet_Ptr ArraySet::Difference( ArraySet_Ptr pList ) throw()
{
	if( pList == NULL )
		return (ArraySet*) Clone();

	ArraySet_Ptr pA = this;
	ArraySet_Ptr pB = pList;
		
	pA->Sort();
	pB->Sort();
	
	ID_TYPE CountC = pA->get_Count();
	ArraySet_Ptr pC = new ArraySet( CountC );	
	
	if( CountC )
	{
		pC->pFinish =STD:: set_difference(	
								pA->pStart, pA->pFinish, 
								pB->pStart, pB->pFinish, 
								pC->pStart );	
	}
	
	pC->isSorted = true;

	if( pC->get_IsEmpty() )
		return NULL; 
	else
		return pC;
}


/**********************************************************************************************/
// Make new list of adresses - difference of pA and pB.
//
ArraySet_Ptr ArraySet::SymmetricDifference( ArraySet_Ptr pList ) throw()
{
	if( pList == NULL )
		return (ArraySet*) Clone();

	ArraySet_Ptr pA = this;
	ArraySet_Ptr pB = pList;
		
	pA->Sort();
	pB->Sort();
	
	ID_TYPE CountC = pA->get_Count() + pB->get_Count();
	ArraySet_Ptr pC = new ArraySet( CountC );	
	
	if( CountC )
	{
		pC->pFinish = STD::set_symmetric_difference( 
								pA->pStart, pA->pFinish, 
								pB->pStart, pB->pFinish, 
								pC->pStart );
	}
			
	pC->isSorted = true;

	if( pC->get_IsEmpty() )
		return NULL; 
	else
		return pC;
}


/**********************************************************************************************/
// Execute current operation on lists pResList and pList.
// It make (pResList op= pList), i.e it don't create additional ArraySet.
//
ArraySet_Ptr ArraySet::MakeOperation( 
		ArraySet_Ptr 		inLeftSet, 
		SetOperation	inOperation,
		ArraySet_Ptr 		inRightSet ) throw()
{
	FBL_CHECK( inLeftSet && inRightSet );

	ArraySet_Ptr pNewRes;

	switch( inOperation )
	{
		case kIntersection:		
				pNewRes = inLeftSet->Intersection( inRightSet );
				break;
		
		case kUnion:
				pNewRes = inLeftSet->Union( inRightSet );
				break;
		
		case kMinus:		
				pNewRes = inLeftSet->Difference( inRightSet );
				break;
				
		case kXOR:		
				pNewRes = inLeftSet->SymmetricDifference( inRightSet );
				break;
	}

	return pNewRes;	
}


#pragma mark -


/**********************************************************************************************/
void ArraySet::AppendItems( ID_TYPE* pArray, ulong inCount )
{
	ID_TYPE* pNext = pArray;
	 
	if( pFinish + inCount >= pStorageEnd )	// must be free place
	{
		ID_TYPE NewSize = (pStorageEnd - pStart) ? (ID_TYPE)2 * (pStorageEnd - pStart) : (ID_TYPE)100;
		Resize( NewSize ); 
	}
	
	while( inCount-- )
		*pFinish++ = *pNext++;		

	isSorted = false;
}


/**********************************************************************************************/
void ArraySet::AppendItemsReverse( ID_TYPE* pArray, ulong inCount )
{
	ID_TYPE* pNext = pArray;
	 
	if( pFinish + inCount >= pStorageEnd )	// must be free place
	{
		ID_TYPE NewSize = (pStorageEnd - pStart) ? ID_TYPE( 2 * (pStorageEnd - pStart) ) 
												 : ID_TYPE( 100 );
		Resize( NewSize ); 
	}
	
	while( inCount-- )
		*pFinish++ = *pNext--;		

	isSorted = false;
}


/**********************************************************************************************/
void ArraySet::InsertItem ( ulong inPos, ID_TYPE inItem )
{
	/*if( pFinish + 1 >= pStorageEnd )	// must be place
	{
		ID_TYPE NewSize = (pStorageEnd - pStart) ? (ID_TYPE)2 * (pStorageEnd - pStart) : (ID_TYPE)100;
		Resize( NewSize ); 
	}*/

	ulong theCount = get_Count();

	FBL_CHECK( pFinish < pStorageEnd );	// must be place
	FBL_CHECK( inPos <= theCount );
	
	ID_TYPE* p = pStart + inPos;
	memmove( p + 1, p, (theCount - inPos) * sizeof(ID_TYPE) );
	
	*p = inItem;
	
	pFinish++;
	isSorted = false;
	
}


/**********************************************************************************************/
void ArraySet::RemoveAt ( ulong inIndex, ulong inCount )
{
	FBL_CHECK( 1 <= inIndex && inIndex <= get_Count() );	// range is 1..
	
	ID_TYPE* p = pStart + inIndex - 1;
	memmove( p, p + inCount, (get_Count() - inIndex - inCount + 1) * sizeof(ID_TYPE) );
	
	pFinish -= inCount;
	
}


/**********************************************************************************************/
// Returns index of the given inItem in the array. 
// Returns 0 if inItem is not found.
// If there is inFrom and inTo then use them as bounds for search (1..Count)
//
ulong ArraySet::FindIndex( ID_TYPE inItem, ulong inFrom, ulong inTo ) 
{
	if( pStart == pFinish )
		return false;
		
	FBL_CHECK( inFrom <= inTo ); 
		
	ID_TYPE*	theStart 	= inFrom ? pStart + (inFrom - 1) : pStart;
	ID_TYPE*	theFinish	= inTo 	 ? pStart + inTo 		: pFinish;
	
	if( theFinish > pFinish )
		theFinish = pFinish;
	
	if( isSorted )
	{
		ID_TYPE* i = STD::lower_bound(theStart, theFinish, inItem);
		
	    if( i != theFinish && ! (inItem < *i) )
				return (ulong)(i - theStart + 1);
		else 	return (ulong)0;

	}else
	{
		// simply iterate array:
		ID_TYPE* p = theStart;
		while( (p < theFinish) && (*p != inItem) )
			p++;
			
		if( p == theFinish )
				return (ulong)0;	
		else 	return (ulong)(p - theStart + 1);	
	}
	
}


/**********************************************************************************************/
FBL_End_Namespace
